3.7.53 Rewrites Tutorial Exercise 2

Here is the rule set:

     [ fib(n) := fib(n, 1, 1) :: integer(n) :: n >= 1,
       fib(1, x, y) := x,
       fib(n, x, y) := fib(n-1, y, x+y) ]

The first rule turns a one-argument fib that people like to write into a three-argument fib that makes computation easier. The second rule converts back from three-argument form once the computation is done. The third rule does the computation itself. It basically says that if ‘x’ and ‘y’ are two consecutive Fibonacci numbers, then ‘y’ and ‘x+y’ are the next (overlapping) pair of Fibonacci numbers.

Notice that because the number ‘n’ was “validated” by the conditions on the first rule, there is no need to put conditions on the other rules because the rule set would never get that far unless the input were valid. That further speeds computation, since no extra conditions need to be checked at every step.

Actually, a user with a nasty sense of humor could enter a bad three-argument fib call directly, say, ‘fib(0, 1, 1)’, which would get the rules into an infinite loop. One thing that would help keep this from happening by accident would be to use something like ‘ZzFib’ instead of fib as the name of the three-argument function.